package 面试;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 满减优惠 {

    public static List<List<Double>> getWays(double[] weights, double limit) {
        List<List<Double>> ans = new ArrayList<>();
        List<Double> tmp = new ArrayList<>();
        // 我认为排个序后更有利于递归处理
        Arrays.sort(weights);
        doCalculate(ans, tmp, weights, limit);
        return ans;
    }

    public static void doCalculate(List<List<Double>> ans, List<Double> tmp,
                                   double[] weights, double limit) {
        // 递归结束的条件
        if (limit < 0.0) { // 偷个懒，虽然我知道不能用 = 号判断浮点数是否相等
            return;
        }
        if (noRemainCapacity(weights, limit)) {
            ans.add(new ArrayList<>(tmp));
            return;
        }
        // 由于同一个商品可以添加多次，所以不设置去重操作
        for (int i = 0; i < weights.length; i++) {
            tmp.add(weights[i]);
            doCalculate(ans, tmp, weights, limit - weights[i]);
            tmp.remove(tmp.size() - 1);
        }
    }

    /**
     *  该方法的意思就是检查当前剩余购物的空间，能否再装点物品进去
     *  实现方式就是检查剩余空间能否装下最小的物品
     * @param weights 物品重量数组
     * @param limit 剩余可以装的重量
     * @return 若不能装了返回 true
     */
    public static boolean noRemainCapacity(double[] weights, double limit) {
        double min = Double.MAX_VALUE;
        for (int i = 0; i < weights.length; i++) {
            if (weights[i] < min) {
                min = weights[i];
            }
        }
        return limit < min ? true : false;
    }

    public static void main(String[] args) {
        double[] weights = {3.4, 3.0, 2.0, 1.3, 4.5, 5.0};
        double limit = 11.0;
        List<List<Double>> ans = getWays(weights, limit);
        ans.forEach(e -> System.out.println(e));
    }
}
